package com.cyan.learn;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;

public class TempTest {

    public int maximalSquare(char[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        int max = 0;

        // dp数组存储正方形的边长
        int[][] dp = new int[m][n];
        if (matrix[0][0] == '0') {
            dp[0][0] = 0;
        } else {
            dp[0][0] = 1;
            max = 1;
        }

        for (int i = 1; i < m; i++) {
            if (matrix[i][0] == '0') {
                dp[i][0] = 0;
            } else {
                dp[i][0] = 1;
                max = Math.max(max, dp[i][0]);
            }
        }
        for (int i = 1; i < n; i++) {
            if (matrix[0][i] == '0') {
                dp[0][i] = 0;
            } else {
                dp[0][i] = 1;
                max = Math.max(max, dp[0][i]);
            }
        }

        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][j] == '0') {
                    dp[i][j] = 0;
                } else {
                    if (dp[i][j - 1] != 0 && dp[i - 1][j] != 0) {
                        int min = Math.min(dp[i - 1][j], dp[i][j - 1]);
                        if (matrix[i - min][j - min] == '0') {
                            dp[i][j] = min;
                        } else {
                            dp[i][j] = min + 1;
                        }
                    } else {
                        dp[i][j] = 1;
                    }
                }
                max = Math.max(max, dp[i][j]);
            }
        }

        return max * max;
    }

    public int lengthOfLongestSubstring(String s) {
        int left = 0, right = 0;
        int max = 0;
        HashSet<Character> set = new HashSet<>();
        while (right < s.length()) {
            if (!set.contains(s.charAt(right))) {
                set.add(s.charAt(right++));
                max = Math.max(max, set.size());
            } else {
                while (left <= right && set.contains(s.charAt(right))) {
                    set.remove(s.charAt(left++));
                }
            }
        }
        return max;
    }

    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> list = new ArrayList<>();

        Arrays.sort(nums);
        if (nums[0] > 0) {
            return list;
        }
        for (int i = 0; i < nums.length; i++) {
            int left = i + 1, right = nums.length - 1;
            if (nums[i] > 0) {
                break;
            }
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum == 0) {
                    list.add(Arrays.asList(nums[i], nums[left], nums[right]));
                    while (right > left && nums[right] == nums[right - 1]) right--;
                    while (right > left && nums[left] == nums[left + 1]) left++;
                    right--;
                    left++;
                } else if (sum < 0) {
                    left++;
                } else {
                    right--;
                }
            }
        }

        return list;
    }

    @Test
    public void test() {
        List<List<Integer>> list = threeSum(new int[]{1,0,-1});
        System.out.println(list);
    }

}